#include <stdio.h>
#include <stdlib.h>

typedef struct Node_ {
  int data;
  struct Node_ *next;
} Node;

static void print_list(Node *head) {
  int i;
  Node *p;
  printf("list: ");
  for (i = 0, p = head; i < 15 && p != NULL; p = p->next, ++i) {
    printf("%d -> ", p->data);
  }
  printf("\n");
}

static void free_list(Node *head) {
  Node *p;
  int i;
  
  if (NULL == head)
    return;
  
  for (i = 0; i < 10; ++i) {
    p = head;
    head = head->next;
    free(p);
  }
}

/* check if cycle is existing */
static Node *check(const Node *head) {
  const Node *slow, *fast;
  if (NULL == head)
    return NULL;

  for (slow = head, fast = head->next;
       fast != NULL && fast->next != NULL;
       slow = slow->next, fast = fast->next->next)
    if (slow == fast)
      return (Node *)slow;

  return NULL;
}

/* if there is no cycle */
static int is_joined_simple(Node *h1, Node *h2) {
  while (h1->next != NULL)
    h1 = h1->next;

  while (h2->next != NULL)
    h2 = h2->next;

  return h1 == h2;
}

/* if there could exist cycle */
int is_joined(Node *h1, Node *h2) {
  Node *cycle1 = check(h1);
  Node *cycle2 = check(h2);
  Node *fast, *slow;

  /* none has cycle */
  if (NULL == cycle1 && NULL == cycle2)
    return is_joined_simple(h1, h2);

  /* one has cycle, the other hasn't */
  if ((NULL == cycle1 && cycle2 != NULL) ||
      (cycle1 != NULL && NULL == cycle2))
    return 0;

  /* both have cycle */
  fast = cycle1;
  slow = cycle1;
  while (1) {
    if (fast == cycle2 || fast->next == cycle2)
      return 1;
    fast = fast->next->next;
    slow = slow->next;
    if (fast == slow)
      return 0;
  }
}

static void list_create1(Node **h1, Node **h2) {
  Node *p;
  int a1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int a2[10] = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  int i;
  
  for (*h1 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;

    p->next = *h1;
    p->data = a1[i-1];
    *h1 = p;
  }

  for (*h2 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;

    p->next = *h2;
    p->data = a2[i-1];
    *h2 = p;
  }
}

static void list_create2(Node **h1, Node **h2) {
  Node *p, *p1, *p2;
  int a1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int a2[10] = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  int i;
  
  for (*h1 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;

    p->next = *h1;
    p->data = a1[i-1];
    *h1 = p;
  }

  for (*h2 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;
    if (10 == i)
      p2 = p;

    if (4 == i)
      p1 = p;
    
    p->next = *h2;
    p->data = a2[i-1];
    *h2 = p;
  }

  p2->next = p1;
}

static void test1() {
  Node *h1, *h2;
  list_create1(&h1, &h2);
  printf("is_joined = %d\n", is_joined(h1, h2));
  print_list(h1);
  print_list(h2);
  
  free_list(h1);
  free_list(h2);

  printf("\n");
}

static void test2() {
  Node *h1, *h2;
  list_create2(&h1, &h2);
  printf("is_joined = %d\n", is_joined(h1, h2));
  print_list(h1);
  print_list(h2);
  
  free_list(h1);
  free_list(h2);

  printf("\n");
}

static void list_create3(Node **h1, Node **h2) {
  Node *p, *p1, *p2;
  int a1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int a2[10] = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  int i;
  
  for (*h1 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;

    if (10 == i)
      p2 = p;

    if (4 == i)
      p1 = p;

    p->next = *h1;
    p->data = a1[i-1];
    *h1 = p;
  }
  p2->next = p1;

  for (*h2 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;
    
    p->next = *h2;
    p->data = a2[i-1];
    *h2 = p;
  }
}

static void test3() {
  Node *h1, *h2;

  list_create3(&h1, &h2);
  printf("is_joined = %d\n", is_joined(h1, h2));
  print_list(h1);
  print_list(h2);
  
  free_list(h1);
  free_list(h2);

  printf("\n");
}

static void list_create4(Node **h1, Node **h2) {
  Node *p, *p1, *p2;
  int a1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int a2[10] = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  int i;
  
  for (*h1 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;

    if (10 == i)
      p2 = p;

    if (4 == i)
      p1 = p;

    p->next = *h1;
    p->data = a1[i-1];
    *h1 = p;
  }
  p2->next = p1;

  for (*h2 = NULL, i = 4; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return;
    if (4 == i)
      p2 = p;
    
    p->next = *h2;
    p->data = a2[i-1];
    *h2 = p;
  }
  p2->next = p1;
}

static void test4() {
  Node *h1, *h2, *p;
  int i;
  list_create4(&h1, &h2);
  printf("is_joined = %d\n", is_joined(h1, h2));
  print_list(h1);
  print_list(h2);
  
  for (i = 0; i < 4; ++i) {
    p = h2;
    h2 = h2->next;
    free(p);
  }
  free_list(h1);

  printf("\n");
}


int main() {
  test1();
  test2();
  test3();
  test4();
  
  return 0;
}
